package oj.oj_572;

/**
 * 另一棵树的子树
 * https://leetcode.cn/problems/subtree-of-another-tree/
 */

import oj.oj_144.TreeNode;
import java.util.*;

class Solution {
    // 找到所有 val 是 带查找目标的结点，填充到 List 中
    // 在 root 为根的树中进行遍历，找到 root.target == val
    // 填充到 ans 中
    private void searchAll(TreeNode root, int target, List<TreeNode> ans) {
        if (root == null) {
            return;
        }

        if (root.val == target) {
            ans.add(root);
        }

        searchAll(root.left, target, ans);
        searchAll(root.right, target, ans);
    }

    // 判断两棵树是否相同
    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }

        if (p == null || q == null) {
            return false;
        }

        return p.val == q.val
                && isSameTree(p.left, q.left)
                && isSameTree(p.right, q.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        List<TreeNode> ans = new ArrayList<>();
        searchAll(root, subRoot.val, ans);
        // ans 中保存了所有待查找的

        for (TreeNode r : ans) {
            if (isSameTree(r, subRoot)) {
                // 存在一个相同的情况
                return true;
            }
        }

        // 一个都没有
        return false;
    }
}